package algorithm.leetcode.I401to600;


/**
 * 来源是Q377,背包的组合问题
 * 题目中有一个暗示的地方: 初始的数组的和不会超过 1000
 * dp过程有点像数字金字塔从上往下算那个,两个dp数组来回倒腾
 */

// eg: [2,1,1,2], 4
// sum       -6 -5 -4 -3 -2 -1 +0 +1 +2 +3 +4 +5 +6
// round0                       1
// round1                 1           1
// round2              1     1     1     1
// round3           1     2     2     2     1
// round4     1     2     3     4     3     2     1


public class Q494 {

    public int findTargetSumWays(int[] nums, int target) {
        // dp数组的含义是i-1000这个数字被组成的次数
        int[] dp = new int[2001];
        dp[1000] = 1;
        for (int num : nums) {
            int[] backup = dp;
            dp = new int[2001];
            for (int i = 0; i < backup.length; i++) {
                if (backup[i] != 0) {
                    dp[i-num] += backup[i];
                    dp[i+num] += backup[i];
                }
            }
        }
        return dp[target+1000];
    }

}
